#include "SupportFunctions.h"

/*
*TO CHECK: IT SEEMS THAT ELEMENT AT RETURN A REFERENCE OF THE SOLUTION IN THE LIST
*IN THIS WAY MODIFIED ELEMENT IS USELESS BUT IT DOESNT UPDATE THE CONTROL VARIABLE
*/
list recoverSolution(list l, int* P, int KSolution, int** matrix, int* a, int* c)
{
	int i=0;
	solution stemp;
	while(i<*P)
	{
		if(elementAt(l,i).control == 0)
		{
			stemp = elementAt(l,i);	//Save the solution to modify in a temp variable solution
			l = backtracking(l,&stemp,i,P,KSolution,matrix,a,c);
			l = modifyElementAt(l,stemp,i);	//return the modified list with the element at index i modified
		}
		i++;
	}
	return l;
}

list backtracking(list l, solution* stemp, int elementIndex, int* P, int KSolution, int** matrix, int* a, int* c)
{
	int t = stemp->i;		//Solution row
	int j = stemp->j;		//Solution column
	int z = stemp->value;	//Objective function value
	int j1 = stemp->j;		//Original solution column (used in searchAlternativeSolution)		
	int temp;				//temp value

	int zcum = 0;

	while(t>0)
	{
		t -= a[j];
		z -= c[j];
		zcum += c[j];

		stemp->x[j] += 1;

		for(temp=j; temp>=0; temp--)
			if(matrix[t][temp] == z)
				break;

		j = temp;

		if(SEARCH_ALT_SOLUTIONS)	//search for alternative solution
			if(t>0)			
				l = searchAlternativeSolution(t,j,zcum,j1,elementIndex,l,P,KSolution, matrix, a, c);
		
		j1 = j;
	}

	stemp->control = 1; //the solution is setted!
	return l;
}

list searchAlternativeSolution(int t, int j, int zcum, int j1, int i, list l, int* P, int KSolution, int** matrix, int* a, int* c)
{
	int index;		//General index
	int s;		//From the first column to the column j1
	int g = 0;	//Index of the alternative solution
	solution stemp1, stemp2;	//temporary solutions that can be inserted in the final solution list 
	solution stempAtIndex = elementAt(l,i); //instead of calling always elementAt we will use the image of this solution

	for(s=0; s<=j1; s++)
	{
		if(s!=j)
		{
			if(matrix[t][s]>=0)	//valid solution
			{	
				if(matrix[t][s] + zcum >= lastSolutionValue(l))	//A NEW SOLUTION IS FOUND
				{	
					g=0;
					if(*P < KSolution)
						*P = *P + 1;
					stemp1 = initSolutionWithParameters(stempAtIndex.x_dim,NULL,matrix[t][s] + zcum,stempAtIndex.i,stempAtIndex.j,0);
					stemp2 = initSolutionWithParameters(stempAtIndex.x_dim,NULL,matrix[t][s],t,s,0);
					l = insertInOrderSolution(l,stemp1,&g);

					l = backtracking(l,&stemp2,g,P,KSolution,matrix,a,c);

					for(index=0; index<5; index++)
						stemp1.x[index] = stemp2.x[index] + stempAtIndex.x[index];

					stemp1.control = 1;	//The final solution is setted
					l = modifyElementAt(l,stemp1,g);	//update with the final solution
					l = keepFirstNElements(l,KSolution);	//Keep only the first K elements in the list
					
					if(stemp2.value >= lastSolutionValue(l))	//ANOTHER NEW SOLUTION IS FOUND
					{
						if(*P < KSolution)
							*P = *P + 1;
						l = insertInOrderSolution(l,stemp2,&g);
						l = keepFirstNElements(l,KSolution);	//Keep only the first K elements in the list
					}
					
				}
			}
		}
	}
	return l;
}